Many databases determine where to store data depending on certain properties of the data, such as how often the data is requested or how often it appears in various sources. For example, in a database that indexes phrases appearing in a body of documents, the system may store phrases that appear most frequently in one type of storage and phrases that rarely appear in documents in another type of storage. Such disparate locations may be referred to as tiers. Key items, such as phrases, may be assigned to a tier based on the number of associated items, such as documents, the key item has. The mapping of key items to a tier may be referred to as a tier-map and the tier storing a key item may indicate how popular the item is. For example, a low level tier may map to key items with less than 100 associated items while the top level tier may store key items that have millions of associated items. In some systems tiers may limit the number of associated items that a key item may have in the tier. For example, if a key item resides in tier 0 it may not have more than 100 associated items. If a new association arises for a key item in tier 0 that already has 100 associated items the system cannot store the new association until the key data item migrates to a tier that allows a larger number of associated items. This delay may result in data loss. In some systems, the tier map can be taken offline to migrate the key items to a new tier. However, in an always-live system dealing with hundreds of billions of records, where associated items are added and updated on a rolling basis, a taking the tier map offline for a full migration of all the records associated with a particular key item can be impractical or even impossible.